class Solution:

    def maxEnvelopes(self, envelopes):
        # 长度相同不能套娃
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        return self.lis([i[1] for i in envelopes])

    def lis(self, nums):
        from bisect import bisect_left
        dp = []
        for i in range(len(nums)):
            idx = bisect_left(dp, nums[i])
            if idx == len(dp):
                dp.append(nums[i])
            else:
                dp[idx] = nums[i]
        return len(dp)


res = Solution().maxEnvelopes([[5,4],[6,4],[6,7],[2,3]])
print(res)
